MOD = 10 ** 9 + 7

dp = [[0] * 1001 for _ in range(1001)]
dp[0][0] = 1
for k in range(1, 1001):
    for n in range(k, 1001):
        # 把最小的放到第1个的情况
        v1 = dp[n - 1][k - 1]

        # 把最小的放到第1个以后位置(n-1个选择)的情况
        v2 = (n - 1) * dp[n - 1][k]

        dp[n][k] = (v1 + v2) % MOD


class Solution:
    def rearrangeSticks(self, nn: int, kk: int) -> int:
        return dp[nn][kk]


if __name__ == "__main__":
    # 自制用例
    print(Solution().rearrangeSticks(1, 1))  # 1
    print(Solution().rearrangeSticks(2, 1))  # 1

    print(Solution().rearrangeSticks(3, 2))  # 3
    print(Solution().rearrangeSticks(5, 5))  # 1
    print(Solution().rearrangeSticks(20, 11))  # 647427950

    # 自制用例
    print(Solution().rearrangeSticks(4, 2))  # 11

    # 测试用例14/50
    print(Solution().rearrangeSticks(105, 20))  # 680986848

    # 测试用例30/50
    print(Solution().rearrangeSticks(469, 311))  # 334833811

    # 测试用例34/50
    print(Solution().rearrangeSticks(964, 564))  # 31307112
